package nan.Binarytree;

import java.util.LinkedList;
import java.util.Queue;

class Node{
    String val;
    Node left;
    Node right;

    public Node(String val) {
        this.val = val;
    }
}
public class Test {
    //创建一个树
    public static Node build(){
        Node a=new Node("A");
        Node b=new Node("B");
        Node c=new Node("C");
        Node d=new Node("D");
        Node e=new Node("E");
        Node f=new Node("F");
        Node g=new Node("G");
        a.left=b;
        a.right=c;
        b.left=d;
        b.right=e;
        e.left=g;
        c.right=f;
        return a;
    }

    //先序遍历
    public static void preOrder(Node root){
        if(root==null){
            return;
        }
        //访问根节点，此处的访问就是打印操作
        System.out.print(root.val);
        //递归遍历左子树。再递归遍历右子树
        preOrder(root.left);
        preOrder(root.right);
    }

    //中序遍历
    public static void inOrder(Node root){
        if(root==null){
            return;
        }
        //先要递归处理左子树
        inOrder(root.left);
        System.out.print(root.val);
        //再处理右子树
        inOrder(root.right);
    }

    //遍历树，记录节点个数
    public static int count=0;//用count来记录元素个数
    public static void length(Node root){
        if(root==null){
            return;
        }
        //访问根节点，此时的操作就是count++
        count++;
        length(root.left);//递归处理左子树
        length(root.right);//递归处理右子树
    }
    public static int length2(Node root){
        if(root==null){
            return 0;
        }
        //当前树的个数=根节点个数+左子树的节点个数+右子树的节点个数
        return 1+length2(root.left)+length2(root.right);
    }

    // 遍历思路-求叶子结点个数
    public static int leafSize=0;
    public static void getLeafSize(Node root){
        if(root==null){
            return;
        }
        if(root.right==null&&root.left==null){
            leafSize++;
        }
        getLeafSize(root.left);
        getLeafSize(root.right);
    }
    public static int getLeafSize2(Node root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafSize2(root.left)+getLeafSize2(root.right);
    }

    //子问题思路-求第 k 层结点个数
    public static int getKLevelSize(Node root,int k){
        if(root==null||k<1){
            return 0;
        }
        if(k==1){
            return 1;//如果当前树非空，第一层节点一定是一个元素
        }
        return getKLevelSize(root.left,k-1)+getKLevelSize(root.right,k-1);
    }

    //求二叉树的高度getHeight
    //求A的高度=1+B的高度和C的高度的较大值
    public static int getHeight(Node root){
        if(root==null){
            return 0;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        if(leftHeight>rightHeight){
            return 1+leftHeight;
        }
        return 1+rightHeight;
    }

    // 查找 val 所在结点，没有找到返回 null
    //// 按照 根 -> 左子树 -> 右子树的顺序进行查找
    //// 一旦找到，立即返回，不需要继续在其他位置查找
    public static Node find(Node root,String toFind){
        if(root==null){
            return null;
        }
        if(root.val.equals(toFind)){
            return root;
        }
        Node result=find(root.left,toFind);
        if(result!=null){
            return result;
        }
        return find(root.right,toFind);
    }

    //后序遍历
    public static void postOrder(Node root){
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val);
    }

    //层序遍历
    public static void levelOrder(Node root){
        if(root==null){
            return;
        }
        Queue<Node> queue=new LinkedList<>();//Queue是一个接口
        queue.offer(root);
        while(true){
            Node cur=queue.poll();
            if(cur==null){
                break;
            }
            //访问当前节点，用打印表示访问
            System.out.print(cur.val);
            //把该节点左子树如队列，右子树入队列
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(root.right!=null){
                queue.offer(cur.right);
            }
        }
    }

    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(Node root){
        if(root==null){
            return true;
        }
        //分成两个阶段来进行判定
        //这个变量为false，表示当前是第一阶段，变量为true，表示进入第二阶段
        boolean isLevel2=false;
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
        while(true) {
            Node cur = queue.poll();
            if (cur == null) {
                break;
            }
            if(!isLevel2){
                //第一阶段的逻辑
                if(cur.left!=null&&cur.right!=null){
                    //继续往下遍历，但是左右子树要入队列
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }else if(cur.left==null&&cur.right!=null){
                    //第一阶段中发现只有右子树的节点，说明这个树一定不是完全二叉树
                    return false;
                }else if(cur.left!=null&&cur.right==null){
                    //遇到了不符合第一阶段要求的节点，进入第二阶段继续进行判断
                    isLevel2=true;
                    queue.offer(cur.left);
                }else{
                    //这个节点没有子树
                    //也是进入第二阶段
                    isLevel2=true;
                }
            }else{
                //第二阶段的逻辑
                if(cur.left!=null||cur.right!=null){
                    return false;
                }
            }
        }
        return true;
    }


    public static void main(String[] args) {
        Node root=build();
        preOrder(root);
        System.out.println();
        inOrder(root);
        System.out.println();
        postOrder(root);
        System.out.println();
        System.out.println(length2(root));
        getLeafSize(root);
        System.out.println(leafSize);
        System.out.println(getHeight(root));
        System.out.println(find(root,"G"));
        levelOrder(root);
    }
}
